/*
 * Copyright (C) 2011 mAPPn.Inc
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.mol.market.common.util;

import java.util.ArrayList;
import java.util.List;

/**
 * 逻辑处理工具
 * 
 * @author debug
 * 
 */
public class BooleanLogicUtil {
    private static final int SKIP = -1;
    private static final int LEFT = 0;
    private static final int RIGHT = 1;
    private static final int NOT = 2;
    private static final int BIT_AND = 3;
    private static final int BIT_NOR = 4;
    private static final int BIT_OR = 5;
    private static final int AND = 6;
    private static final int OR = 7;
    private static final int TEXT = 8;
    private char[] operator;
    private String patten;
    private LogicRunner g;

    public BooleanLogicUtil(String patten) {
        this.patten = patten;
        operator = patten.toCharArray();
        List<int[]> excuter = new ArrayList<int[]>();
        List<int[]> stack = new ArrayList<int[]>();
        int last = -1;
        // 词法分析
        for (int i = 0; i < operator.length;) {
            int[] result = parseOperator(operator, i, operator.length);
            if (result[0] != SKIP) {
                excuter.add(result);
                if (result[0] == LEFT) {
                    stack.add(result);
                } else if (result[0] == RIGHT) {
                    if (stack.size() == 0) {
                        throw new IllegalArgumentException(getMessage(result,
                                "missing '('"));
                    } else {
                        stack.remove(stack.size() - 1);
                    }
                }
                if (result[0] == RIGHT && last == LEFT) {
                    throw new IllegalArgumentException(getMessage(result, null));
                }
                last = result[0];
            }
            i += result[2];
        }
        if (stack.size() > 0) {
            throw new IllegalArgumentException(getMessage(
                    stack.get(stack.size() - 1), "missing ')'"));
        }
        // 语法分析
        g = parseAll(excuter, new int[] { 0 }, new LogicRunner[] { null },
                false);
        if (g == null
                || (g.type == TEXT && g.v == null || g.type != TEXT
                        && (g.r1 == null || (g.type != NOT && g.r2 == null)))) {
            throw new IllegalArgumentException("not completed\n'" + patten
                    + "'");
        }
    }

    public boolean excute(CallBack<String, Boolean> callback) {
        return g.excute(callback);
    }


    public String toString() {
        return g.toString();
    }

    /**
     * 解析字符表达式
     * 
     * @param excuter
     *            经过词法分析后的表达式组列表
     * @param index
     *            [待处理的表达式组下标]
     * @return 逻辑运算解释器
     */

    private LogicRunner parse(List<int[]> excuter, int[] index) {
        int[] op = excuter.get(index[0]++);
        if (op[0] == TEXT) {
            return new LogicRunner(TEXT, null, null,
                    new int[] { op[1], op[2] }, operator);
        } else if (op[0] == NOT) {
            LogicRunner tmp = null;
            while ((tmp = parse(excuter, index)) == null)
                ;
            return new LogicRunner(NOT, tmp, null, new int[] { op[1], op[2] },
                    operator);
        } else if (op[0] == LEFT) {
            return parseAll(excuter, index, new LogicRunner[] { null }, false);
        } else {
            throw new IllegalArgumentException(getMessage(op, null));
        }
    }

    /**
     * 添加表达式
     * 
     * @param result
     *            [逻辑运算解释器]
     * @param tmp
     *            当前逻辑运算解释器
     * @param op
     *            当前表达式组
     * @param fastReturn
     *            是否迅速返回可执行的最短逻辑运算解释器
     * @return 是否迅速返回可执行的最短逻辑运算解释器
     */
    private boolean tryAdd(LogicRunner[] result, LogicRunner tmp, int[] op,
            boolean fastReturn) {
        if (result[0] == null) {
            result[0] = tmp;
            return false;
        } else if (result[0].type == TEXT || result[0].type == NOT
                || result[0].r1 == null || result[0].r2 != null) {
            throw new IllegalArgumentException(getMessage(op, null));
        } else {
            result[0].r2 = tmp;
            return fastReturn;
        }
    }

    /**
     * 解析逻辑表达式语法，创建逻辑运算解释器
     * 
     * @param excuter
     *            经过词法分析后的表达式组列表
     * @param index
     *            [待处理的表达式组下标]
     * @param result
     *            [逻辑运算解释器]
     * @param fastReturn
     *            是否迅速返回可执行的最短逻辑运算解释器
     * @return 逻辑运算解释器
     */
    private LogicRunner parseAll(List<int[]> excuter, int[] index,
            LogicRunner[] result, boolean fastReturn) {
        if (index[0] >= excuter.size()) {
            throw new IllegalArgumentException("not completed\n'" + patten
                    + "'");
        }
        // 逐条解析表达式组
        while (index[0] < excuter.size()) {
            LogicRunner tmp = null;
            int[] op = excuter.get(index[0]++);
            switch (op[0]) {
            case TEXT:
                // 当前表达式组为字符组时，直接添加至解释器末尾
                tmp = new LogicRunner(TEXT, null, null, new int[] { op[1],
                        op[2] }, operator);
                if (tryAdd(result, tmp, op, fastReturn)) {// 如果需要迅速返回可执行的最短逻辑运算解释器，返回当前解释器
                    return result[0];
                }
                break;
            case NOT:
                // 当前表达式组为单目逻辑运算组时，先尝试解析后面的运算符组，再添加至解释器末尾
                while ((tmp = parse(excuter, index)) == null)
                    ;
                tmp = new LogicRunner(NOT, tmp, null,
                        new int[] { op[1], op[2] }, operator);
                if (tryAdd(result, tmp, op, fastReturn)) {// 如果需要迅速返回可执行的最短逻辑运算解释器，返回当前解释器
                    return result[0];
                }
                break;
            case BIT_AND:
            case BIT_NOR:
            case BIT_OR:
            case AND:
            case OR:
                // 当前表达式组为双目逻辑运算组时
                if (result[0] == null
                        || result[0].type != TEXT
                        && (result[0].r1 == null || (result[0].type != NOT && result[0].r2 == null))) {
                    // 如果运算符左侧为空，或者左侧为不完整的运算符，抛出非法参数异常
                    throw new IllegalArgumentException(getMessage(op, null));
                } else if (needSplit(result[0], op[0])) {
                    // 如果运算符左侧逻辑运算解释器优先级低于当前运算符优先级，抢占左侧逻辑运算解释器的末位操作数，做为当前运算组的第1操作数，将合并后的当前运算组置为左侧逻辑运算解释器的末位操作数
                    change(excuter, index, result, op);
                } else {
                    // 如果运算符左侧逻辑运算解释器优先级高于当前运算符优先级，将左侧逻辑运算解释器置为当前运算组的第1操作数，并将当前运算组添加至解释器末尾
                    result[0] = new LogicRunner(op[0], result[0], null,
                            new int[] { op[1], op[2] }, operator);
                }
                break;
            case LEFT:
                // 当前表达式组为左括号时,递归解析后续表达式组
                while ((tmp = parseAll(excuter, index,
                        new LogicRunner[] { null }, false)) == null)
                    ;
                // 标记得到的逻辑运算解释器为原子解释器，并将当前运算组添加至解释器末尾
                tmp.splitable = false;
                if (tryAdd(result, tmp, op, fastReturn)) {// 如果需要迅速返回可执行的最短逻辑运算解释器，返回当前解释器
                    return result[0];
                }
                break;
            case RIGHT:
                // 当前表达式组为右括号时，返回当前解释器
                if (result[0] != null
                        && (result[0].type == TEXT && result[0].v == null || result[0].type != TEXT
                                && (result[0].r1 == null || (result[0].type != NOT && result[0].r2 == null)))) {
                    throw new IllegalArgumentException(getMessage(op, null));
                } else {
                    return result[0];
                }
            default:
                throw new IllegalArgumentException(getMessage(op, null));
            }
        }
        return result[0];
    }

    /**
     * 归位表达式组
     * 
     * @param excuter
     *            经过词法分析后的表达式组列表
     * @param index
     *            [待处理的表达式组下标]
     * @param result
     *            [逻辑运算解释器]
     * @param op
     *            待归位的表达式组
     */
    private void change(List<int[]> excuter, int[] index, LogicRunner[] result,
            int[] op) {
        if (needSplit(result[0].r2, op[0])) {
            change(excuter, index, new LogicRunner[] { result[0].r2 }, op);
        } else {
            result[0].r2 = new LogicRunner(op[0], result[0].r2, null,
                    new int[] { op[1], op[2] }, operator);
            parseAll(excuter, index, new LogicRunner[] { result[0].r2 }, true);
        }
    }

    /**
     * 判断已解析的表达式优先级是否低于当前表达式的优先级
     * 
     * @param logic
     *            已解析的表达式
     * @param type
     *            当前表达式类型
     * @return
     */
    private boolean needSplit(LogicRunner logic, int type) {
        return logic.splitable && type > NOT && type < OR
                && logic.type > BIT_AND && logic.type < TEXT
                && logic.type > type;
    }

    /**
     * 生成错误信息
     * 
     * @param op
     * @param msg
     * @return
     */
    private String getMessage(int[] op, String msg) {
        StringBuilder sb = new StringBuilder(msg == null ? "something wrong :"
                : msg);
        sb.append('\n');
        for (int i = 0; i < operator.length; i += 80) {
            sb.append(operator, i, operator.length - i < 80 ? operator.length
                    - i : 80);
            sb.append('\n');
            if (op[1] - i >= 0 && op[1] - i < 80) {
                for (int j = op[1] - i; j > 0; j--) {
                    sb.append(' ');
                }
                sb.append("^\n");
            }
        }
        return sb.substring(0, sb.length() - 1);
    }

    /**
     * 逻辑表达式词法分析
     * 
     * @param operator
     *            待分析的表达式
     * @param start
     *            表达式起始点
     * @param end
     *            表达式截止点
     * @return [表达式类型,表达式起点,表达式长度]
     */

    private int[] parseOperator(char[] operator, int start, int end) {
        int[] result = new int[3];
        result[0] = SKIP;
        result[1] = start;
        result[2] = end - start;

        // 逐个判断操作符类型
        while (start < end) {
            int p = SKIP;
            if (operator[start] == '(') {
                p = LEFT;
            } else if (operator[start] == ')') {
                p = RIGHT;
            } else if (operator[start] == '!') {
                p = NOT;
            } else if (operator[start] == '^') {
                p = BIT_NOR;
            } else if (operator[start] == '&') {
                p = AND;
            } else if (operator[start] == '|') {
                p = OR;
            } else if ((operator[start] >= '0' && operator[start] <= '9')
                    || (operator[start] >= 'a' && operator[start] <= 'z')
                    || (operator[start] >= 'A' && operator[start] <= 'Z')
                    || operator[start] == '_' || operator[start] == '.'
                    || operator[start] == '-') {
                p = TEXT;
            } else if (operator[start] != ' ') {
                throw new IllegalArgumentException("illegal character '"
                        + operator[start] + "' from '" + patten + "'");
            }

            if (result[0] == SKIP) {// 上一个操作符无效的情况
                result[0] = p;
                if (p == NOT || p == BIT_NOR || p == LEFT || p == RIGHT
                        || p == SKIP) {// 当前操作符长度是1或无效操作符时，返回当前操作符
                    result[2] += start + 1 - end;
                    break;
                }
            } else {// 上一个操作符有效的情况
                if (result[0] != p || (p == AND || p == OR)
                        && (result[2] + start - end) >= 2) {// 当前操作符与上一个操作符类型不一致符或者已匹配到的操作符满足有效长度的时候，返回已匹配到的操作符
                    if (result[2] + start - end == 1) {
                        result[0] = result[0] == AND ? BIT_AND
                                : result[0] == OR ? BIT_OR : result[0];
                    }
                    result[2] += start - end;
                    break;
                }
            }
            start++;
        }
        return result;
    }

    /**
     * 逻辑运算解释器
     * 
     * @author debug
     * 
     */
    private static class LogicRunner {
        int type;
        LogicRunner r1;

        LogicRunner r2;
        int[] v;
        char[] operator;
        boolean splitable;

        public LogicRunner(int type, LogicRunner g1, LogicRunner g2, int[] v,
                char[] operator) {
            this.type = type;
            this.r1 = g1;
            this.r2 = g2;
            this.v = v;
            this.operator = operator;
            splitable = true;
        }

        /**
         * 执行逻辑运算
         * 
         * @param callback
         * @return
         */
        boolean excute(CallBack<String, Boolean> callback) {
            switch (type) {
            case TEXT:
                return callback.run(new String(operator, v[0], v[1]));
            case NOT:
                return !r1.excute(callback);
            case BIT_AND:
                return r1.excute(callback) & r2.excute(callback);
            case BIT_NOR:
                return r1.excute(callback) ^ r2.excute(callback);
            case BIT_OR:
                return r1.excute(callback) | r2.excute(callback);
            case AND:
                return r1.excute(callback) && r2.excute(callback);
            case OR:
                return r1.excute(callback) || r2.excute(callback);
            default:
                throw new IllegalArgumentException("type : " + type);
            }
        }


        public String toString() {
            switch (type) {
            case TEXT:
                return new String(operator, v[0], v[1]);
            case NOT:
                return "(" + new String(operator, v[0], v[1]) + r1 + ")";
            case BIT_AND:
            case BIT_NOR:
            case BIT_OR:
            case AND:
            case OR:
                return "(" + r1 + " " + new String(operator, v[0], v[1]) + " "
                        + r2 + ")";
            default:
                return "";
            }
        }
    }
    
    public interface CallBack<K, V> {
        V run(K x);
    }
}
